# 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：n >= 3
#  对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
#  给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。
#  （回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8]
# 是 [3, 4, 5, 6, 7, 8] 的一个子序列）
#
#  示例 1：
# 输入: arr = [1,2,3,4,5,6,7,8]
# 输出: 5
# 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
#
#  示例 2：
# 输入: arr = [1,3,7,11,12,14,18]
# 输出: 3
# 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
from typing import List


class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        """
        动态规划
        思路:
        每一个起始对都要遍历后面的数组剩余的元素能否记录状态,用以不用重复遍历

        将斐波那契子序列中的两个连续项A[i], A[ j] 视为单结点(i, j)，整个子序列是这些连续结点之间的路径
        例如 A = [1,2,3,4,5,6,7,8.9,11,13]
        对于斐波那契式的子序列(A[1] = 2, A[2] = 3, A[4] = 5, A[7] = 8, A[10] =13)，结点之间的路径为
        (1, 2) <-> (2, 4) <-> (4, 7) <-> (7, 10)
        可得:只有当A[i] + A[j] = A[k]时(i,j) (j,k)才是连通的(i,j,k均是指数组下标)

        原问题与子问题:
           1.子问题:求解(i,j)为  结尾  的fib子序列的长度

           2.设计状态:dp(i,j)表示(i,j)结尾的fib子序列的长度

           3.状态转移方程:
              if (A[i] + A[j] == A[k])
                 dp(j,k) = dp(i,j) + 1
              目标值 = max(dp(i,j))
           4.边界值: dp(i,j) = 2(fib子序列最短也会有两个)
        :param arr:
        :return:
        """
        res = 0
        size = len(arr)
        arrIndexMap, dpMap = {}, {}  # 存arr元素和对应的索引, dpMap[i * len(arr) + j] = m 表示(i,j)结尾的fib子序列的长度为m
        # 之所以能用一个int表示(i,j)是因为i,j都不相同(i < j)那么 [i * n + j (n为数组长度或者更大的数,不然可能会冲突)]一定唯一(二维变一维小技巧)
        for i, num in enumerate(arr):
            arrIndexMap[num] = i
        for k in range(size):
            for j in range(0, k, 1):
                if (i := arrIndexMap.get(arr[k] - arr[j])) is not None and i < j:  # 说明能在j前面找到一个i 使得(A[i] == A[k] - A[j])
                    dpIJ = dpMap[i * size + j] if i * size + j in dpMap else 2
                    dpJK = dpIJ + 1
                    dpMap[j * size + k] = dpJK  # dpJK = dpIJ + 1
                    res = max(res, dpJK)
        return res if res > 2 else 0


if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7, 8]
    # arr = [1, 3, 7, 11, 12, 14, 18]
    print(Solution().lenLongestFibSubseq(arr))
